/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    let head = new ListNode()
    let tail = head //维护新链表尾部
    while (list1 && list2) { //向新链表尾部插入小的元素
        if (list1.val <= list2.val) {
            tail.next = list1
            list1 = list1.next
        } else {
            tail.next = list2
            list2 = list2.next
        }
        tail = tail.next //只插入一个，移动到尾部
    }
    //合并剩余的节点
    tail.next = list1 === null ? list2 : list1
    return head.next //head是空节点，下一个才是第一个结点
};